package com.gitee.feizns.explore.data_structure.array.easy;

/**
 * @author feizns
 * @since 2020/1/9
 */
public class MaxProfit {

    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}, 5));
    }

//    public static int maxProfit(int[] prices) {
//        int max = 0;
//        for (int i = 0; i < prices.length; i++) {
//            for (int j = i + 1; j < prices.length; j++) {
//                max = Math.max(prices[j] - prices[i], max);
//            }
//        }
//        return max;
//    }

//    public static int maxProfit(int[] prices) {
//        int min = prices[0];
//        int ans = 0;
//        for (int i = 1; i < prices.length; i++) {
//            if ( prices[i] < min )
//                min = prices[i];
//            else
//                ans = Math.max(prices[i] - min, ans);
//        }
//        return ans;
//    }

    public static int maxProfit(int[] prices) {
        int min = prices[0];
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            if ( prices[i] < min )
                min = prices[i];
            else
                ans = Math.max(prices[i] - min, ans);
        }
        return ans;
    }

    static int min = Integer.MAX_VALUE;

    public static int maxProfit(int[] prices, int end) {
        if ( end == 0 ) {
            min = prices[end];
            return 0;
        }

        int profit = maxProfit(prices, end - 1);
        min = Math.min(min, prices[end]);
        return Math.max(profit, prices[end] - min);
    }

}
